//正则表达式匹配（hard）: https://leetcode.cn/problems/regular-expression-matching/
class Solution
{
public:
	bool isMatch(string s, string p)
	{
		int m = s.size(), n = p.size();
		s = ' ' + s, p = ' ' + p;
		// 1. 创建 dp 表
		vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
		// 2. 初始化
		dp[0][0] = true;
		for (int j = 2; j <= n; j += 2)
			if (p[j] == '*') dp[0][j] = true;
			else break;
		// 3. 填表
		for (int i = 1; i <= m; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (p[j] == '*')
					dp[i][j] = dp[i][j - 2] || (p[j - 1] == '.' || p[j - 1] ==
						s[i]) && dp[i - 1][j];
				else
					dp[i][j] = (p[j] == s[i] || p[j] == '.') && dp[i - 1][j -
					1];
			}
		}
		// 4. 返回值
		return dp[m][n];
	}
};

